We derive the convergence rate depending on the mixing coefficients, minimum and maximum pairwise distances between the true centers, dimensionality and number of components; and obtain a near-optimal local contraction radius. While there have been some recent notable works that derive local convergence rates for EM in the two symmetric mixture of Gaussians, in the more general case, the derivations need structurally different and non-trivial arguments. We use recent tools from learning theory and empirical processes to achieve our theoretical results.

Summary: This paper derives statistical guarantees for the gradient EM algorithm applied to clustering in Gaussian mixture models, generalizing the results of [1] to multiple clusters and non-uniform cluster weights. The first result (Theorem 1) concerns the "population EM algorithm", i.e., when the expectation step can be computed exactly rather than being estimated from data. For this case, if the cluster centers are sufficiently separated and all the estimated cluster centers are initialized sufficiently close to the true cluster centers (i.e., roughly if there is already a sufficiently clear 1-1 correspondence between the estimated and true cluster centers), then the estimated cluster centers converge linearly to the true centers. This result relies on first showing (Theorem 4) that, under these conditions, due to properties of the Gaussian distribution, the curvature of the Q function is bounded (i.e., specifically, the gradient is Lipschitz). By a standard proof, the Lipschitz gradient then implies convergence of gradient descent.

In this paper, we study convergence properties of the gradient variant of Expectation-Maximization algorithm \cite{lange1995gradient} for Gaussian Mixture Models for arbitrary number of clusters and mixing coefficients. We derive the convergence rate depending on the mixing coefficients, minimum and maximum pairwise distances between the true centers, dimensionality and number of components; and obtain a near-optimal local contraction radius. While there have been some recent notable works that derive local convergence rates for EM in the two symmetric mixture of Gaussians, in the more general case, the derivations need structurally different and non-trivial arguments. We use recent tools from learning theory and empirical processes to achieve our theoretical results. Papers published at the Neural Information Processing Systems Conference.